package com.problem.stack;

import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/longest-well-performing-interval/
 */
public class LongestWPI {
    //给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
    //
    //我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
    //
    //所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
    //
    //请你返回「表现良好时间段」的最大长度。
    //
    // 
    //
    //示例 1：
    //
    //输入：hours = [9,9,6,0,6,6,9]
    //输出：3
    //解释：最长的表现良好时间段是 [9,9,6]。
    // 
    //
    //提示：
    //
    //1 <= hours.length <= 10000
    //0 <= hours[i] <= 16



    //二分查找
    public int longestWPI(int[] hours) {
        int res=0;
        int n = hours.length;
        //1.得分的前缀和
        int[] sum = new int[hours.length+1];
        sum[0] = 0;
        for (int i=0;i<hours.length;++i) {
            sum[i+1] = sum[1] + hours[i]>8?1:-1;
        }


        int mx = 0;
        int[] prefix = new int[n+1];
        prefix[0] = 0;
        for (int i=1;i<=n;++i) {
            mx = Math.min(sum[i],mx);
            prefix[i] = mx;
        }

        for (int i=1;i<=n;++i) {
            int l=0;
            int r=i-1;
            while (l <= r) {
                int mid = l +(r-1)/2;
                if (prefix[mid] >= sum[i]) {
                    l = mid + 1;
                } else {
                    r = mid-1;
                }

            }
            res = Math.max(res,i-(r+1));
        }
        return res;
    }


    //todo 看不懂！
    public int xx(int[] hours) {
        int n=hours.length;
        int []a=new int[n+1];//前缀和
        int []mn=new int[n+1];
        int []mn_pos=new int[n+1];
        for (int i=1;i<=n;i++) if (hours[i-1]>8) a[i]=1; else a[i]=-1;
        a[0]=0;
        for (int i=1;i<=n;i++) a[i]+=a[i-1];

        mn[0]=a[0];mn_pos[0]=0;
        for (int i=1;i<=n;i++){
            if (a[i]<mn[i-1]){
                mn[i]=a[i];
                mn_pos[i]=i;
            }
            else {
                mn[i]=mn[i-1];
                mn_pos[i]=mn_pos[i-1];
            }
        }

        int ans=0;
        for (int i=1;i<=n;i++){
            int k=a[i];
            int l=0,r=i;
            while (l<r){
                int mid=(l+r)/2;
                if (mn[mid]<k) r=mid;
                else l=mid+1;
            }
            if (l==i&&hours[l-1]<=8) continue;
            ans=Math.max(ans,i-mn_pos[l]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int [] a = new int[]{9,9,6,0,6,6,9};
        System.out.println(new LongestWPI().xx(a));
    }

    //O(n^2)
//    public int longestWPI(int[] hours) {
//        int result=0;
//        for (int i=0;i<hours.length;i++) {
//            int n = 0;
//            int c=0;
//            for (int j=i;j<hours.length;j++) {
//                if (hours[j] > 8) {
//                    c += 1;
//                } else {
//                    c -=1;
//                }
//                if (c > 0) {
//                    n = j-i+1;
//                }
//
//            }
//            if (n > result) {
//                result = n;
//            }
//        }
//        return result;
//    }
}

